package _03_recursion;

import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/2 - 13:10
 * 杨辉三角（使用记忆法优化，带二维数组缓存）
 * 不带缓存打印高度10的三角时，调用 getValue 函数 1991 次
 * 带缓存调用 127 次
 *
 * ①
 * ① ①
 * ① ② ①
 * ① ③ ③ ①
 * ① ④ ⑥ ④ ①
 */
public class PascalTriangleTest2_cache {

    // 控制台打印杨辉三角(带缓存)
    @Test
    public void test() {
        print(10);
    }

    /**
     * 给出行号i和列j，求出该位置元素的值(带缓存)
     *
     * @param i
     * @param j
     * @return
     */
    int getValue(int[][] cache, int i, int j) {
        if (j > i) {
            throw new IllegalArgumentException();
        }
        if (cache[i][j] == 0) { // 缓存未命中
            if (j == 0 || i == j) {
                cache[i][j] = 1;
            } else {
                cache[i][j] = getValue(cache, i - 1, j - 1) + getValue(cache, i - 1, j);
            }
        }
        return cache[i][j];
    }

    /**
     * 打印杨辉三角(带缓存)
     *
     * @param row 高度
     */
    void print(int row) {
        // 缓存数组
        int[][] cache = new int[row][];
        for (int i = 0; i < row; i++) {
            cache[i] = new int[i + 1];
            // 打印前置的空格
            for (int k = 0; k < row - i - 1; k++) {
                System.out.print("\t");
            }
            for (int j = 0; j < i + 1; j++) {
                System.out.print(getValue(cache, i, j) + "\t\t");
            }
            System.out.println();
        }
    }
}
